import java.util.Arrays;
import java.util.Comparator;

/**
 * 快速选择或者堆排序
 * 找到未排序数组中的第k个最大元素。请注意，它是排序顺序中的第k个最大元素，而不是第k个不同元素
 */
public class SortLookUp {
    //    第一种方法 快速排序
    public static void swap(Integer[] nums,int i,int j){
        if(i==j){
            return;
        }
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    public int quickSelect(Integer[] nums,int left,int right,int k) {
        if(left>right){
            return 0;
        }
        int i=left;
        int j=right;
        while(i<j){
            while(i<j && nums[j]<=nums[left]){
                System.out.println(j+"---"+nums[j]);
                j--;
            }
            while(i<j && nums[i]>=nums[left]){
                i++;
            }
            swap(nums,i,j);
        }
        swap(nums,left,j);
        if(k==i-left+1){ //从哪一个序列开始的，相差一个left:k：总的序列，left：当前序列
            System.out.println("第一种方法输出结果是："+nums[i]);
            return nums[i];
        }
        else if(k<i-left+1){
            return quickSelect(nums,left,i-1,k);
        } else{
            return quickSelect(nums,i+1,right,k);
        }
    }

    //    第二种方法 堆排序
    public static void heapSort(Integer[] array,int k) {
        new HeapSort().heapSort(array);
        for(Integer i:array){
            System.out.println("第二种方法："+i);
        }
        System.out.println("第二种方法输出结果是："+array[array.length-k]);
    }

    //    第三种方法 普通
    public  void generalSort(Integer[] nums, int key) {
        Arrays.sort(nums,new MyComparator());
        for (int num :
                nums) {
            System.out.println(num);
        }
        System.out.println("第三种方法输出结果是："+nums[key-1]);

    }

    //    主函数  测试
    public static void main(String[] args) {
        Integer[] nums={3,2,1,5,6,4};
        int key=2;
//        new SortLookUp().generalSort(nums,key);
        new SortLookUp().heapSort(nums,key);
//        new SortLookUp().quickSelect(nums,0,nums.length-1,key);
    }
    class MyComparator implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            if(o1<o2){
                return 1;
            }else if(o1>o2){
                return -1;
            } else{
                return 0;
            }
        }
    }
}
